Steiner system

In combinatorial mathematics, a Steiner system (named after Jakob Steiner) is a type of block design, specifically a t-design with λ = 1 and t ≥ 2.

A Steiner system with parameters t, k, n, written S(t,k,n), is an n-element set S together with a set of k-element subsets of S (called blocks) with the property that each t-element subset of S is contained in exactly one block. In an alternate notation for block designs, an S(t,k,n) would be a t-(n,k,1) design.

This definition is relatively modern, generalizing the classical definition of Steiner systems which in addition required that k = t + 1. An S(2,3,n) was (and still is) called a Steiner triple system, while an S(3,4,n) was called a Steiner quadruple system, and so on. With the generalization of the definition, this naming system is no longer strictly adhered to.

Contents

Examples

Finite projective planes

A finite projective plane of order q, with the lines as blocks, is an S(2, q+1, q2+q+1), since it has q2+q+1 points, each line passes through q+1 points, and each pair of distinct points lies on exactly one line.

Finite affine planes

A finite affine plane of order q, with the lines as blocks, is an S(2, q, q2). An affine plane of order q can be obtained from a projective plane of the same order by removing one block and all of the points in that block from the projective plane. Choosing different blocks to remove in this way can lead to non-isomorphic affine planes.

Classical Steiner systems

Steiner triple systems

An S(2,3,n) is called a Steiner triple system, and its blocks are called triples. It is common to see the abbreviation STS(n) for a Steiner triple system of order n. The number of triples is n(n−1)/6. A necessary and sufficient condition for the existence of an S(2,3,n) is that n \equiv 1 or 3 (mod 6). The projective plane of order 2 (the Fano plane) is an STS(7) and the affine plane of order 3 is an STS(9).

Up to isomorphism, the STS(7) and STS(9) are unique, there are two STS(13)s, 80 STS(15)s, and 11,084,874,829 STS(19)s. [1]

We can define a multiplication on the set S using the Steiner triple system by setting aa = a for all a in S, and ab = c if {a,b,c} is a triple. This makes S an idempotent, commutative quasigroup. It has the additional property that "ab" = "c" implies "bc" = "a" and "ca" = "b". Conversely, any (finite) quasigroup with these properties arises from a Steiner triple system.

Steiner quadruple systems

An S(3,4,n) is called a Steiner quadruple system. A necessary and sufficient condition for the existence of an S(3,4,n) is that n \equiv 2 or 4 (mod 6). The abbreviation SQS(n) is often used for these systems.

Up to isomorphism, SQS(8) and SQS(10) are unique, there are 4 SQS(14)s and 1,054,163 SQS(16)s.[2]

Steiner quintuple systems

An S(4,5,n) is called a Steiner quintuple system. A necessary condition for the existence of such a system is that n \equiv 3 or 5 (mod 6) which comes from considerations that apply to all the classical Steiner systems. An additional necessary condition is that n \not\equiv 4 (mod 5), which comes from the fact that the number of blocks must be an integer. Sufficient conditions are not known.

There is a unique Steiner quintuple system of order 11, but none of order 15 or order 17.[3] Systems are known for orders 23, 35, 47, 71, 83, 107, 131, 167 and 243. The smallest order for which the existence is not known (as of 2011) is 21.

Properties

It is clear from the definition of S(t,k,n) that 1 < t < k < n. (Equalities, while technically possible, lead to trivial systems.)

If S(t,k,n) exists, then taking all blocks containing a specific element and discarding that element gives a derived system S(t−1,k−1,n−1). Therefore the existence of S(t−1,k−1,n−1) is a necessary condition for the existence of S(t,k,n).

The number of t-element subsets in S is \tbinom n t, while the number of t-element subsets in each block is \tbinom k t. Since every t-element subset is contained in exactly one block, we have \tbinom n t = b\tbinom k t, or b = \frac{\tbinom nt}{\tbinom kt}, where b is the number of blocks. Similar reasoning about t-element subsets containing a particular element gives us \tbinom{n-1}{t-1}=r\tbinom{k-1}{t-1}, or r=\frac{\tbinom{n-1}{t-1}}{\tbinom{k-1}{t-1}}, where r is the number of blocks containing any given element. From these definitions follows the equation bk=rn. It is a necessary condition for the existence of S(t,k,n) that b and r are integers. As with any block design, Fisher's inequality b\ge n is true in Steiner systems.

It can be shown that if there is a Steiner system S(2,k,n), where k is a prime power greater than 1, then n \equiv 1 or k (mod k(k−1)). In particular, a Steiner triple system S(2,3,n) must have n = 6m+1 or 6m+3. It is known that this is the only restriction on Steiner triple systems, that is, for each natural number m, systems S(2,3,6m+1) and S(2,3,6m+3) exist.

History

Steiner triple systems were defined for the first time by W.S.B. Woolhouse in 1844 in the Prize question #1733 of Lady's and Gentlemens' Diary.[4] The posed problem was solved in (Kirkman 1847). In 1850 Kirkman posed a variation of the problem known as Kirkman's schoolgirl problem, which asks for triple systems having an additional property (resolvablity). Unaware of Kirkman's work, Jakob Steiner reintroduced triple systems in (Steiner 1853), and as this work was more widely known, the systems were named in his honor.

Mathieu groups

Several examples of Steiner systems are closely related to group theory. In particular, the finite simple groups called Mathieu groups arise as automorphism groups of Steiner systems:

The Steiner system S(5, 6, 12)

There is a unique S(5,6,12) Steiner system; its automorphism group is the Mathieu group M12, and in that context it is denoted by W12.

Constructions

To construct it, take a 12-point set and think of it as the projective line over F11 — in other words, the integers mod 11 together with a point called infinity. Among the integers mod 11, six are perfect squares:

\{0,1,3,4,5,9\}.\

Call this set a "block". From this, we may obtain other blocks by applying fractional linear transformations:

z \mapsto \frac{az %2B b}{cz %2B d}.

These blocks then form a (5,6,12) Steiner system.

W12 can also constructed from the affine geometry on the vector space F3xF3, an S(2,3,9) system.

An alternative construction of W12 is the 'Kitten' of R.T. Curtis.[5]

The Steiner system S(5, 8, 24)

Particularly remarkable is the Steiner system S(5, 8, 24), also known as the Witt design or Witt geometry. It was described in a 1931 paper by R.D. Carmichael and rediscovered by Ernst Witt, who published a paper on the subject in 1938: (Witt 1938). This system is connected with many of the sporadic simple groups and with the exceptional 24-dimensional lattice known as the Leech lattice.

The automorphism group of S(5, 8, 24) is the Mathieu group M24, and in that context the design is denoted W24 ("W" for "Witt")

Constructions

There are many ways to construct the S(5,8,24). The method given here is perhaps the simplest to describe, and is easy to convert into a computer program. It uses sequences of 24 bits. The idea is to write these down in lexicographic order, missing out any one which differs from some earlier one in fewer than 8 positions. The result looks like this:

   000000000000000000000000
   000000000000000011111111
   000000000000111100001111
   000000000000111111110000
   000000000011001100110011
   000000000011001111001100
   000000000011110000111100
   000000000011110011000011
   000000000101010101010101
   000000000101010110101010
   .
   . (next 4083 omitted)
   .
   111111111111000011110000
   111111111111111100000000
   111111111111111111111111

The list contains 4096 items, which are each code words of the extended binary Golay code. They form a group under the XOR operation. One of them has zero 1-bits, 759 of them have eight 1-bits, 2576 of them have twelve 1-bits, 759 of them have sixteen 1-bits, and one has twenty-four 1-bits. The 759 8-element blocks of the S(5,8,24) (called octads) are given by the patterns of 1's in the code words with eight 1-bits.

A still more direct approach is taken by running through all 8-element subsets of a 24-element set and skipping any such subset which differs from some octad already found in fewer than four positions.

Departing from 01, 02, 03, ..., 22, 23, 24 one obtains

   01 02 03 04 05 06 07 08
   01 02 03 04 09 10 11 12
   01 02 03 04 13 14 15 16
   . 
   . (next 753 octads omitted)
   .
   13 14 15 16 17 18 19 20
   13 14 15 16 21 22 23 24
   17 18 19 20 21 22 23 24

Each single element occurs 253 times somewhere in some octad. Each pair occurs 77 times. Each triple occurs 21 times. Each quadruple (tetrad) occurs 5 times. Each quintuple (pentad) occurs once. Not every hexad, heptad or octad occurs.

See also

Notes

  1. ^ Colbourn & Dinitz 2007, pg.60
  2. ^ Colbourn & Dinitz 2007, pg.106
  3. ^ Östergard & Pottonen 2008
  4. ^ Lindner & Rodger 1997, pg.3
  5. ^ (Curtis 1984)

References

External links